package com.binarysearch;

import java.util.Arrays;

public class Solution1498 {
    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int mode = 1_0000_0000_7;
        int[] pow = new int[len];
        pow[0] = 1;
        for (int i = 1; i < len; i++) {
            pow[i] = 2 * pow[i - 1];
            pow[i] %= mode;
        }
        int i = 0;
        int j = len - 1;
        int res = 0;
        while (i <= j) {
            if (nums[i] + nums[j] <= target) {
                res += pow[j - i];
                res %= mode;
                i++;
            } else j--;
        }
        return res;
    }
}
